package chapter04_RecursionAndDynamic;

/**
 * 描述：
 *      字符串交错
 * @author hl
 * @date 2021/7/6 22:06
 */
public class IsCross {

    public boolean isCross1(String str1, String str2, String aim) {
        if(str1 == null || str2 == null || aim == null || str1.length() + str2.length() != aim.length()){
            return false;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        char[] aimArr = aim.toCharArray();
        char[] more = chars1.length >= chars2.length ? chars1 : chars2;
        char[] less = chars1.length < chars2.length ? chars1 : chars2;
        boolean[] dp = new boolean[less.length + 1];
        dp[0] = true;
        for (int i = 1; i < less.length; i++) {
            dp[i] = dp[i - 1] && less[i - 1] == aimArr[i - 1];
        }
        for (int i = 1; i < more.length; i++) {
            dp[0] = dp[0] && more[i - 1] == aimArr[i - 1];
            for (int j = 1; j < less.length; j++) {
                dp[j] = (dp[j] && more[i - 1] == aimArr[i + j - 1]) || (dp[j - 1] && less[j - 1] == aimArr[i + j - 1]);
            }
        }
        return dp[less.length];
    }
}
